package com.zhongge.singlelistOJ;
/**
 * @ClassName SingleLinkedList
 * @Description TODO 模拟实现泛型单向无头非循环链表
 * @Author 笨忠
 * @Date 2025/8/8 18:07
 * @Version 1.0
 */
@SuppressWarnings("all")
public class SingleLinkedList< E > {

    //首地址（火车头）
    public Node<E> head;

    //节点类
    private static class Node<E> {
        //数值域
        public E val;
        //地址域
        public Node<E> next;

        public Node(E val) {
            this.val = val;
        }
    }
    /**
     * 手动创建一个单链表
     */
    public void createSingleList() {
        Node<Integer> node1 = new Node<>(23);
        Node<Integer> node2 = new Node<>(12);
        Node<Integer> node3 = new Node<>(56);
        Node<Integer> node4 = new Node<>(78);

        //构建起来链表
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;

        this.head = (Node<E>)node1;
    }

    //头插法
    public void addFirst(E data) {
        //得有元素
        Node<E> node = new Node<>(data);
        //先绑后
        node.next = head;
        //头变新
        head = node;
    }

    //尾插法
    public void addLast(E data) {
        Node<E> node = new Node<>(data);
        //处理特殊情况
        if (this.head == null) {
            head = node;
            return;
        }
        //找尾巴
        Node<E> cur = this.head;
        while (cur.next != null) {
            cur = cur.next;
        }
        //绑后
        cur.next = node;
    }

    //任意位置插入,第一个数据节点为0号下标
    public boolean addIndex(int index,E data) {
        if (index < 0 || index > size()) {
            throw new RuntimeException("索引不合法");
        }
        //头插
        if (index == 0) {
            addFirst(data);
            return true;
        }
        //尾插
        if (index == size()) {
            addLast(data);
            return true;
        }
        //中间插
        //找到前驱节点
        Node<E> prev = findPrevNode(index);
        if (prev == null) {
            return false;
        }
        Node<E> node = new Node<>(data);
        //绑后
        node.next = prev.next;
        //绑前
        prev.next = node;

        return true;
    }

    private Node<E> findPrevNode(int index) {
        Node<E> prev = this.head;
        int count = 0;
        while (count < index - 1) {
            prev = prev.next;
            count++;
        }
        return prev;
    }

    //查找是否包含关键字key是否在单链表当中
    public boolean contains(E key) {
        Node<E> cur = this.head;
        while (cur != null) {
            if (cur.val.equals(key)) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
    //删除第一次出现关键字为key的节点
    public void remove(E key) {
        if (this.head == null) {
            return;
        }
        if (head.val.equals(key)) {
            //首后移
            this.head = this.head.next;
            return;
        }
        //走到合理就是删除中间和后面
        //找到前驱节点
        Node<E> prev = findPrevNode(key);
        if (prev == null) {
            return;
        }
        //拿到当前节点
        Node<E> curDel = prev.next;
        prev.next = curDel.next;

    }

    private Node<E> findPrevNode(E key) {
        Node<E> prev = this.head;
        while (prev.next != null) {
            if (prev.next.val.equals(key)) {
                return prev;
            }
            prev = prev.next;
        }
        return null;
    }

    //删除所有值为key的节点要求在o(N)时间内删除==》双指针
    public void removeAllKey(E key) {
        //如果节点本身就空==》就没必要删除
        if (head == null) {
            return;
        }
        Node<E> prev = this.head;
        Node<E> cur = this.head.next;

        while (cur != null) {
            if (cur.val.equals(key)) {
                prev.next = cur.next;
                cur = cur.next;
            } else {
                //确保prev是cur的直接前驱
                //所以两个同时往后移动
                prev = cur;
                cur = cur.next;
            }
        }
        //首节点单独处理
        if (head.val.equals(key)) {
            //首变型
            head = head.next;
        }
    }

    public void clear() {
        Node<E> cur = this.head;
        while (cur != null) {
            //你在前面等我
            Node<E> curN = cur.next;
            //我处理完本节点
            cur.val = null;
            cur.next = null;
            //我再来找你
            cur = curN;
        }
        //最后将head指针置为null
        this.head = null;
    }

    //得到单链表的长度
    public int size() {
        Node<E> cur = this.head;
        int count = 0;//计数器
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    /**
     * 打印出链表中的元素
     */
    public void display() {
        Node<E> cur = this.head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

}
